package chapter4;

/**
 * 问题：给定一个矩阵m,从左上角开始每次只能向右或向下移动，最后到达最右下角的位置，
 * 路径上所有的数字累加起来就是路径和，求最小路径和。
 * 扩展：打印最小路径和的路径
 */
public class MinPathSum {
    /**
     * 【动态规划】
     * 求最小路径和，方法1
     * 复杂度O(M*N) O(M*N)
     * 状态转化方程：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];（i > 0, j > 0）
     * dp[i][0] = dp[i - 1][0] + m[i][0];(j = 0)
     * dp[i][0] = dp[i - 1][0] + m[i][0];(i = 0)
     * @param m
     * @return
     */
    public int minPathSum1(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + m[i][0];
        }
        for (int j = 1; j < col; j++) {
            dp[0][j] = dp[0][j - 1] + m[0][j];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
            }
        }
        return dp[row - 1][col - 1];
    }

    /**
     * 【动态规划】
     * 求最小路径和，方法2，使用【空间压缩】
     * 复杂度O(M*N) O(min{M,N})
     * 状态转换方程：dp[j] = Math.min(dp[j-1],dp[j])+min[i][j](M>=N)
     * dp[j] = Math.min(dp[j-1],dp[j])+min[j][i](N>=M)
     * @param m
     * @return
     */
    public int minPathSum2(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        int more = Math.max(m.length, m[0].length);
        int less = Math.min(m.length, m[0].length);
        boolean rowMore = more == m.length;// 行数是否大于列数
        int[] dp = new int[less];
        for(int i = 0; i < less; i++) {
            dp[i] = dp[i-1] + (rowMore ? m[0][i] : m[i][0]);
        }
        for (int i = 1; i < more; i++) {
            for (int j = 1; j < less; j++) {
                dp[j] = Math.min(dp[j - 1], dp[j]) + (rowMore ? m[i][j] : m[j][i]);
            }
        }
        return dp[less - 1];
    }
}
